Có một số giả thuyết về nguồn gốc của từ này. Theo tiếng Sicilia, tính từ mafiusu có lẽ vay mượn từ gốc Arập là mahyas có nghĩa là " ba hoa, hiếu chiến" hay marfud có nghĩa là "đồ bỏ đi". Đại khái được dịch theo nghĩa chung là " thái độ nghênh ngang" hay cả nghĩa " tính gan dạ, anh hùng". Khi liên hệ với một người, theo ý kiến của nhà nghiên cứu Diego Gambetta, mafiusu vào thế kỉ 19 ở Sicilia được hiểu theo các nghĩa là: sự ức hiếp, tính kiêu ngạo, can đảm, mạnh dạn, kiêu hãnh.

Theo nhà dân tộc học người Sicilia Giuseppe Pitrè, mối liên hệ của từ này với những băng đảng tội phạm bí mật mới hình thành ở Sicilia và Ý mới chỉ sau này. Vì thế nguồn gốc từ Mafia mang tính chất hoang đường, lỏng lẻo và rất khó giải thích cặn kẽ. Thuật ngữ "Mafia" sau này được dùng trong cộng đồng Ý như đã nêu trên quả là một hiện tượng kỳ lạ. Từ "Mafia" xuất hiện lần đầu tiên trên công luận vào năm 1865 trong bản báo cáo của quận trưởng thị trấn Palermo ngài Filippo Antonio Gualterio. Leopoldo Franchetti, một quan chức chính phủ Ý tới Sicilia và đã viết một báo cáo cặn kẽ nhất về Mafia vào năm 1876. Ông coi Mafia là "tổ chức bạo lực" và mô tả cấu trúc của Mafia như sau: "Mafia chắc chắn là một hệ thống bạo lực chỉ có điều gọi nó như thế nào và xem nó có ảnh hưởng tới tính chất xã hội cũng như vai trò của nó đối với Sicilia như thế nào thôi. Chúng còn có một số tên gọi biến tướng ở những vùng khác nhau nữa". Ông cho rằng, Mafia ăn sâu bén rễ vào đời sống xã hội của Sicilia và nếu không dập tắt được nó, thì những kiến trúc xã hội của vùng đảo phía nam này sẽ bị nó lấn át.

Tên đích thực: Cosa Nostra

Theo một số thành viên của Mafia thì tên đích thực của Mafia là Cosa Nostra (của chúng ta). Theo tên Mafia đào tẩu Tommaso Buscetta thì từ "Mafia" là sự hư cấu mang tính văn chương. Những tên Mafia đào tẩu khác như Antonio Calderone và Salvatore Contorno cũng nói tương tự. Theo họ, tên thật sự của tổ chức này là "Cosa Nostra". Đối với một người, niềm vinh hạnh đứng trong tổ chức này thì không cần đặt tên cho nó. Các thành viên của Mafia giới thiệu với nhau hay các thành viên khác thuộc về "Cosa Nostra" (việc của chúng ta) hay la stessa cosa (việc giống nhau). Có nghĩa là "anh ta cũng giống như thế, đều là thành viên của Mafia, như anh thôi". Chỉ có những người ngoài thế giới Mafia mới cần tên để gọi chúng, sau đó viết hoa thành "Cosa Nostra".

Cosa Nostra được dùng lần đầu tiên vào năm 1960 ở Mỹ, do một tên là thành viên của Mafia nhưng sau đó ra toà làm nhân chứng. Cũng trong thời gian đó, nó trở thành tên riêng được FBI sử dụng và được các phương tiện thông tin đại chúng phổ biến rộng rãi. Sau đó thuật ngữ này được sử dụng khắp nơi thay thế cho tên gọi Mafia trước đây. Thậm chí FBI còn đề xướng một cách gọi là "La Cosa Nostra", trong tiếng Ý từ "la" được dùng như một mạo từ đứng trước danh từ Mafia, tương tự như "a, the" trong tiếng Anh.

Những tên khác

Trong lịch sử, Mafia mang nhiều tên khác nhau, như: xã hội danh giá. Các thành viên của Mafia cũng tự gọi họ là những con người danh giá.